package com.study.datastructure.sort;

/**
 * 插入排序
 */
public class InsertSort {

    static void sort1(int[] a){

        for(int i=1;i<a.length;i++){
            for (int j = i; j>0 ; j--) {
                if(a[j]<a[j-1]){
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                }
            }
        }
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

    static void sort2(int[] a){

        int middle = a.length/2;


        while(middle>0){
            for(int i=0;i<middle;i++){
                if(a[i]>a[i+middle]){
                    int temp = a[i];
                    a[i] = a[i+middle];
                    a[i+middle] = temp;
                }
            }
            middle = middle/2;
        }


        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

    static void sort3(int[] data){

        int j = 0;
        int temp = 0;
        for (int increment = data.length / 2; increment > 0; increment /= 2) {
            System.out.println("increment:" + increment);
            for (int i = increment; i < data.length; i++) {
                // System.out.println("i:" + i);
                temp = data[i];
                for (j = i - increment; j >= 0; j -= increment) {
                    // System.out.println("j:" + j);
                    // System.out.println("temp:" + temp);
                    // System.out.println("data[" + j + "]:" + data[j]);
                    if (temp < data[j]) {
                        data[j + increment] = data[j];
                    } else {
                        break;
                    }
                }
                data[j + increment] = temp;
            }
            for (int i = 0; i < data.length; i++)
                System.out.print(data[i] + " ");
        }

    }

    public static void main(String[] args) {
        int[] a = new int[]{5,3,6,9,4,7,0};
        sort2(a);
    }

}
